package cn.fxzhang.leetcode.no07;

/**
 * 781. 森林中的兔子
 * 森林中，每个兔子都有颜色。其中一些兔子（可能是全部）告诉你还有多少其他的兔子和自己有相同的颜色。我们将这些回答放在 answers 数组里。
 * 返回森林中兔子的最少数量。
 * 示例:
 * 输入: answers = [1, 1, 2]
 * 输出: 5
 * answers 的长度最大为1000。
 * answers[i] 是在 [0, 999] 范围内的整数。
 *
 * 类型：数学/贪心
 * 题解：将回答相同数字的兔子放到一组，如果满了就增加一组。最后将各组相加就
 * 时间复杂度：O(N)
 * 空间复杂度：O(N)
 *
 * 提交记录(1/1)：
 * 执行用时: 0 ms, 击败了100.00%
 * 内存消耗: 37.8 MB, 击败了62.12%
 *
 * 【中等】通过次数23,452提交次数37,632
 * @author 张晓帆
 * @date 2021/04/04
 */
public class P0781_Rabbits_In_Forest {

    public int numRabbits(int[] answers) {
        int[] capacity =  new int[1000];
        int ans = 0;
        for (int k : answers) {
            // 如果k对应的组放得下，就放到改组，改组容量减1
            if (capacity[k] > 0){
                capacity[k]--;
            } else{
                // 放不下了就新开1组，并将该组的容量累计到答案里
                capacity[k] = k;
                ans += k+1;
            }
        }
        return ans;
    }

}
